{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Binary Subarrays With Sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #prefix-sum #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #前缀和 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numSubarraysWithSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #和相同的二元子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个二元数组 <code>nums</code> ，和一个整数 <code>goal</code> ，请你统计并返回有多少个和为 <code>goal</code> 的<strong> 非空</strong> 子数组。</p>\n",
    "\n",
    "<p><strong>子数组</strong> 是数组的一段连续部分。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,0,1,0,1], goal = 2\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "有 4 个满足题目要求的子数组：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,0,0,0,0], goal = 0\n",
    "<strong>输出：</strong>15\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 <= nums.length <= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>nums[i]</code> 不是 <code>0</code> 就是 <code>1</code></li>\n",
    "\t<li><code>0 <= goal <= nums.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binary-subarrays-with-sum](https://leetcode.cn/problems/binary-subarrays-with-sum/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binary-subarrays-with-sum](https://leetcode.cn/problems/binary-subarrays-with-sum/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,0,1,0,1]\\n2', '[0,0,0,0,0]\\n0']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\r\n",
    "        zeros = []\r\n",
    "        c = 0\r\n",
    "        for n in nums:\r\n",
    "            if n == 1:\r\n",
    "                zeros.append(c)\r\n",
    "                c = 0\r\n",
    "            else:\r\n",
    "                c += 1\r\n",
    "        zeros.append(c)\r\n",
    "        if goal == 0:\r\n",
    "            return sum([n*(n+1)//2 for n in zeros])\r\n",
    "        c = 0\r\n",
    "        for i in range(len(zeros)-goal):\r\n",
    "            c += (zeros[i]+1)*(zeros[i+goal]+1)\r\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A, S):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # A = \"\".join([str(i) for i in A])\n",
    "        if S==0:\n",
    "            res = 0\n",
    "            i=0\n",
    "            while 1:\n",
    "                while i<len(A) and A[i]:\n",
    "                    i+=1\n",
    "                if i==len(A):\n",
    "                    return res\n",
    "                j = i\n",
    "                while j<len(A) and not A[j]:\n",
    "                    j+=1\n",
    "                res+=(j-i)*(j-i+1)//2\n",
    "                if j==len(A):\n",
    "                    break\n",
    "                i = j\n",
    "            return res\n",
    "        if sum(A)<S:\n",
    "            return 0\n",
    "        i = 0\n",
    "        res = 0\n",
    "        left0 = right0 = 0\n",
    "        while not A[i] and i<len(A):\n",
    "            left0+=1\n",
    "            i+=1\n",
    "        j = i\n",
    "        cnt = 1\n",
    "        while cnt<S and j<len(A):\n",
    "            j+=1\n",
    "            cnt+=A[j]\n",
    "        while i<len(A) and j<len(A):\n",
    "            # left0,right0 = 0,0\n",
    "            # while i-left0-1>=0 and not A[i-left0-1]:\n",
    "            #     left0+=1\n",
    "            right0 = 0\n",
    "            while j+right0+1<len(A) and not A[j+right0+1]:\n",
    "                right0+=1\n",
    "            \n",
    "            res += (left0+1)*(right0+1)\n",
    "            # print(i,j,left0,right0,cnt)\n",
    "            left0 = 0\n",
    "            i+=1\n",
    "            while i<len(A) and not A[i]:\n",
    "                left0+=1\n",
    "                i+=1\n",
    "            j+=right0+1\n",
    "            if j==len(A):\n",
    "                break\n",
    "        return res\n",
    "        \n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A, S):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not A:\n",
    "            return 0\n",
    "        ans = 0\n",
    "        l = 0\n",
    "        tot = 0\n",
    "        if not S:\n",
    "            for x in A:\n",
    "                if x:\n",
    "                    ans += tot * (tot + 1) // 2\n",
    "                    tot = 0\n",
    "                else:\n",
    "                    tot += 1\n",
    "            return ans + tot * (tot + 1) // 2\n",
    "        \n",
    "        cnt = [0 for i in range(len(A) + 1)]\n",
    "        for i in range(len(A))[::-1]:\n",
    "            if not A[i]:\n",
    "                cnt[i] = cnt[i + 1] + 1\n",
    "            \n",
    "        for i, x in enumerate(A):\n",
    "            tot += x   \n",
    "            if tot >= S:\n",
    "                while tot > S and l <= i:\n",
    "                    tot -= A[l]\n",
    "                    l += 1\n",
    "                ans += cnt[l] + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A, S):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        result = 0\n",
    "        ones_index = []\n",
    "        for i in range(len(A)):\n",
    "            if A[i] == 1: ones_index.append(i)\n",
    "        #print(ones_index)\n",
    "        if S != 0:\n",
    "            start, end = 0, S - 1\n",
    "            while end < len(ones_index):\n",
    "                if start == 0: start_zeros = ones_index[start] - 0\n",
    "                else: start_zeros = ones_index[start] - ones_index[start - 1] - 1\n",
    "                if end == len(ones_index) - 1: end_zeros = (len(A) - 1) - ones_index[end]\n",
    "                else: end_zeros = ones_index[end + 1] - ones_index[end] - 1\n",
    "                result += (start_zeros + 1) * (end_zeros + 1)\n",
    "                start += 1\n",
    "                end += 1\n",
    "        else:\n",
    "            if sum(A) == 0:\n",
    "                return self.zeros_num(len(A))\n",
    "            else:\n",
    "                zeros_num = []\n",
    "                for i in range(1, len(ones_index)):\n",
    "                    zeros_num.append(ones_index[i] - ones_index[i-1] - 1)\n",
    "                zeros_num = [ones_index[0] - 0] + zeros_num + [len(A) - ones_index[-1] - 1]\n",
    "                #print(zeros_num)\n",
    "                for gap in zeros_num:\n",
    "                    result += self.zeros_num(gap)\n",
    "        return result\n",
    "\n",
    "\n",
    "    def zeros_num(self, gap):\n",
    "        result = 0\n",
    "        for i in range(1, gap + 1):\n",
    "            result += i\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A, S):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        l=len(A)\n",
    "        a=[-1]+[i for i in range(l) if A[i]]+[l]\n",
    "        ans=0\n",
    "        if not S:\n",
    "            for i in range(1,len(a)):\n",
    "                ans+=((a[i]-a[i-1])*(a[i]-a[i-1]-1))//2\n",
    "            return ans\n",
    "        for i in range(S,len(a)-1):\n",
    "            ans+=(a[i-S+1]-a[i-S])*(a[i+1]-a[i])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A, S):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if S == 0:\n",
    "            c_0 = []\n",
    "            i = 0\n",
    "            while i < len(A):\n",
    "                c = 0\n",
    "                while i < len(A) and A[i] == 0:\n",
    "                    c += 1\n",
    "                    i += 1\n",
    "                if c > 0:\n",
    "                    c_0.append(c)\n",
    "                i += 1\n",
    "            return sum([sum([x+1 for x in range(e)]) for e in c_0])\n",
    "        else:\n",
    "            sub = 0\n",
    "            length_A = len(A)\n",
    "            one_index = [idx for idx, val in enumerate(A) if val == 1]\n",
    "            for i in range(0, len(one_index)-S+1):\n",
    "                start = one_index[i]\n",
    "                end = one_index[i+S-1]\n",
    "                # print('i={},start={},end={}'.format(i,start,end))\n",
    "                front = 1\n",
    "                back = 1\n",
    "                while(start > 0):\n",
    "                    start -= 1\n",
    "                    if A[start] == 0:\n",
    "                        front += 1\n",
    "                    else:\n",
    "                        break\n",
    "\n",
    "                while(end < length_A-1):\n",
    "                    end += 1\n",
    "                    if A[end] == 0:\n",
    "                        back += 1\n",
    "                    else:\n",
    "                        break\n",
    "                sub += front * back \n",
    "            return sub"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A, S):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :type S: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        N = len(A)\n",
    "        tsum = [0] * (N+1)\n",
    "        for i in range(1, N + 1):\n",
    "            tsum[i] = tsum[i - 1] + A[i - 1]\n",
    "        res = 0\n",
    "        for i in range(1, N + 1):\n",
    "            remain = tsum[i] - S\n",
    "            if remain < 0:\n",
    "                continue\n",
    "            left = bisect.bisect_left(tsum, remain)\n",
    "            right = bisect.bisect_right(tsum, remain)\n",
    "            right = min(i, right)\n",
    "            res += right - left\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A: 'List[int]', S: 'int') -> 'int':\n",
    "        max_sm = [0] * (len(A) + 1)\n",
    "        max_sm[0] = 1\n",
    "        sm = 0\n",
    "        res = 0\n",
    "        for a in A:\n",
    "            sm += a\n",
    "            if sm >= S:\n",
    "                res += max_sm[sm - S]\n",
    "            max_sm[sm] += 1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A: List[int], S: int) -> int:\n",
    "        #A =[0,0,0,0,0]; S=0\n",
    "        if not A: return 0\n",
    "        def solver(target):\n",
    "            ans = i = window = 0\n",
    "            for j,v in enumerate(A):\n",
    "                window += v\n",
    "                while window>target and i<=j:\n",
    "                    window, i = window-A[i], i+1\n",
    "                ans += j - i +1\n",
    "                #print(i,ans)\n",
    "            return ans\n",
    "        #print(solver(S),solver(S-1))\n",
    "        return solver(S) - solver(S-1)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A: List[int], S: int) -> int:\n",
    "        #S = 0\n",
    "        def atMost(x):\n",
    "            i = 0\n",
    "            res = 0\n",
    "            window = 0\n",
    "            for j,v in enumerate(A):\n",
    "                window += v\n",
    "                while window > x and i<=j:\n",
    "                    window -= A[i]\n",
    "                    i += 1\n",
    "                res += j -i +1\n",
    "            return res\n",
    "        return atMost(S) - atMost(S-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A: List[int], S: int) -> int:\n",
    "        def atmost(k):\n",
    "            res = i = 0\n",
    "            for j in range(len(A)):\n",
    "                k -= A[j]\n",
    "                while i <= j and k < 0:\n",
    "                    k += A[i]\n",
    "                    i += 1\n",
    "                print('i='+str(i))    \n",
    "                res += j-i+1\n",
    "\n",
    "                print(res)\n",
    "            return res\n",
    "        \n",
    "        return atmost(S) - atmost(S-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef numSubarraysWithSum(self,A,S):\n",
    "\t\tans=0\n",
    "\t\tcnt=i=0\n",
    "\t\tstart=0\n",
    "\t\tlegt=len(A)\n",
    "\t\tflag=bool(S)\n",
    "\t\twhile i<legt:\n",
    "\t\t\tcnt+=A[i]\n",
    "\t\t\tif cnt!=S:\n",
    "\t\t\t\ti+=1\n",
    "\t\t\t\tif not flag:\n",
    "\t\t\t\t\tcnt=0\n",
    "\t\t\t\t\tstart=i\n",
    "\t\t\telse:\n",
    "\t\t\t\tri=i+1\n",
    "\t\t\t\twhile flag and ri<legt and not A[ri]:\n",
    "\t\t\t\t\tri+=1\n",
    "\t\t\t\tle=start\n",
    "\t\t\t\twhile flag and le<i and not A[le]:\n",
    "\t\t\t\t\tle+=1\n",
    "\t\t\t\tans+=(le-start+1)*(ri-i) if flag else i-start+1\n",
    "\t\t\t\tstart,i,cnt=le+flag,ri,cnt-flag\n",
    "\t\treturn ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A: List[int], S: int) -> int:\n",
    "        n = len(A)\n",
    "        left1 = left2 = right = 0\n",
    "        windowSum1 = windowSum2 = 0\n",
    "        ret = 0\n",
    "        while right < n:\n",
    "            windowSum1 += A[right]\n",
    "            windowSum2 += A[right]\n",
    "            while windowSum1 > S:\n",
    "                windowSum1 -= A[left1]\n",
    "                left1 += 1\n",
    "            while windowSum2 > S - 1 and left2 <= right:\n",
    "                windowSum2 -= A[left2]\n",
    "                left2 += 1\n",
    "            ret += left2 - left1 \n",
    "            right += 1\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A, S):\n",
    "        def atMostK(A,S):\n",
    "            if S<0:\n",
    "                return 0\n",
    "\n",
    "            l = 0\n",
    "            ans = 0\n",
    "            _sum = 0\n",
    "\n",
    "            for r in range(len(A)):\n",
    "                _sum += A[r]\n",
    "                while _sum > S:\n",
    "                    _sum -= A[l]\n",
    "                    l += 1\n",
    "                ans += (r-l+1)\n",
    "            return ans\n",
    "        return atMostK(A,S) - atMostK(A, S-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A: List[int], S: int) -> int:\n",
    "        sumlo = sumhi = 0\n",
    "        lhi = llo = 0\n",
    "        ans = 0\n",
    "        for i in range(len(A)):\n",
    "            sumlo += A[i]\n",
    "            while llo < i and sumlo > S:  # 计算左端点到i的前缀和\n",
    "                sumlo -= A[llo]\n",
    "                llo += 1\n",
    "\n",
    "            sumhi += A[i]  # 计算右端点到i的前缀和\n",
    "            while lhi < i and (sumhi > S or sumhi == S and not A[lhi]):\n",
    "                sumhi -= A[lhi]\n",
    "                lhi += 1\n",
    "            if sumlo == S:\n",
    "                ans += lhi - llo + 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, A: List[int], S: int) -> int:\n",
    "        if S <= 0:\n",
    "            last1 = -1\n",
    "            res = 0\n",
    "            for i, a in enumerate(A):\n",
    "                if a == 0:\n",
    "                    res += i - last1\n",
    "                else:\n",
    "                    last1 = i\n",
    "            return res\n",
    "        queue = deque([-1])\n",
    "        res = 0\n",
    "        for i, a in enumerate(A):\n",
    "            if a == 1:\n",
    "                queue.append(i)\n",
    "                S -= 1\n",
    "                if S <= 0:\n",
    "                    last1 = queue.popleft()\n",
    "            if S <= 0:\n",
    "                res += queue[0] - last1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        def ltgoal(nums,goal):\n",
    "            if goal<0:\n",
    "                return 0\n",
    "            start = 0\n",
    "            times = 0\n",
    "            count_one = 0\n",
    "            for end in range(len(nums)):\n",
    "                if nums[end] == 1:\n",
    "                    count_one += 1\n",
    "                while count_one > goal:\n",
    "                    if nums[start] == 1:\n",
    "                        count_one -= 1\n",
    "                    start += 1\n",
    "                times += (end-start+1)\n",
    "            return times\n",
    "        return ltgoal(nums,goal)-ltgoal(nums,goal-1)\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def atMostK(self, nums, k):\n",
    "        if not nums:\n",
    "            return 0\n",
    "        l = 0\n",
    "        ret = sum = 0\n",
    "        for r in range(len(nums)):\n",
    "            sum += nums[r]\n",
    "            while sum > k and l < r:\n",
    "                sum -= nums[l]\n",
    "                l += 1\n",
    "            if sum <= k:\n",
    "                ret += r-l+1\n",
    "        return ret\n",
    "\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        if goal == 0:\n",
    "            return self.atMostK(nums, goal)\n",
    "        return self.atMostK(nums, goal) - self.atMostK(nums, goal-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        leftOne, leftTwo, right = 0, 0, 0\n",
    "        segSumOne, sgeSumTwo = 0, 0\n",
    "        numsLen = len(nums)\n",
    "        res = 0\n",
    "        while right < numsLen:\n",
    "            segSumOne += nums[right]\n",
    "            sgeSumTwo += nums[right]\n",
    "            while leftOne <= right and segSumOne > goal:\n",
    "                segSumOne -= nums[leftOne]\n",
    "                leftOne += 1\n",
    "            while leftTwo <= right and sgeSumTwo >= goal:\n",
    "                sgeSumTwo -= nums[leftTwo]\n",
    "                leftTwo += 1\n",
    "            res += leftTwo - leftOne\n",
    "            right += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        #超时写法\n",
    "        # n=len(nums)\n",
    "        # dp=[[0 for _ in range(n+1)] for _ in range(n+1)]\n",
    "        # ans=0\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i,n):\n",
    "        #         dp[i+1][j+1]=dp[i+1][j]+nums[j]\n",
    "        #         if dp[i+1][j+1]==goal:\n",
    "        #             ans+=1\n",
    "        # return ans\n",
    "\n",
    "        #使用滑动窗口+前缀和写法，还是超时\n",
    "        # ans=0\n",
    "        # n=len(nums)\n",
    "        # if nums[0]==goal:\n",
    "        #     ans+=1\n",
    "        # for index in range(1,n):\n",
    "        #     nums[index]+=nums[index-1]\n",
    "        #     left=0\n",
    "        #     if nums[index]==goal:\n",
    "        #         ans+=1\n",
    "        #     while left<index:\n",
    "        #         diff=nums[index]-nums[left]\n",
    "        #         if diff==goal:\n",
    "        #             ans+=1\n",
    "        #         elif diff<goal:\n",
    "        #             break\n",
    "        #         left+=1\n",
    "        # return ans\n",
    "\n",
    "        #使用哈希表用来存储前缀和\n",
    "        # mydict=dict()\n",
    "        # sums,ans=0,0\n",
    "        # for index,num in enumerate(nums):\n",
    "        #     mydict[sums]=mydict.get(sums,0)+1\n",
    "        #     sums+=num\n",
    "        #     ans+=mydict.get(sums-goal,0)\n",
    "        # return ans\n",
    "\n",
    "        #之前的双指针写法有问题，看题解的双指针写法\n",
    "        Po_li,Po_hi=0,0\n",
    "        li_sums,hi_sums=0,0\n",
    "        ans=0\n",
    "        \n",
    "        for index,num in enumerate(nums):\n",
    "            li_sums+=num\n",
    "            '''\n",
    "            为什么需要小于index,而不是小于等于，为了防止越界。\n",
    "            '''\n",
    "            while Po_li<index and li_sums>goal:\n",
    "                li_sums-=nums[Po_li]\n",
    "                Po_li+=1\n",
    "\n",
    "            hi_sums+=num\n",
    "            while Po_hi<index and (hi_sums>goal or (hi_sums==goal and nums[Po_hi]==0)):\n",
    "                hi_sums-=nums[Po_hi]\n",
    "                Po_hi+=1\n",
    "            if hi_sums==goal:\n",
    "                ans+=(Po_hi-Po_li+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        l1,l2 = 0,0\n",
    "        tmp = 0\n",
    "        ans = 0\n",
    "        for idx,i in enumerate(nums):\n",
    "            tmp += i\n",
    "            if tmp == goal:\n",
    "                while l2 < idx and nums[l2] == 0:\n",
    "                    l2 += 1\n",
    "            elif tmp > goal: \n",
    "                while nums[l1] != 1:\n",
    "                    l1 += 1\n",
    "                tmp -= 1\n",
    "                l1 += 1\n",
    "                l2 = l1\n",
    "                while l2 < idx and nums[l2] == 0:\n",
    "                    l2 += 1\n",
    "            else:\n",
    "                continue\n",
    "            print(tmp,l1,l2,idx,ans)\n",
    "            if l2 <= idx:\n",
    "                ans += (l2-l1+1)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        if goal == 0:\n",
    "            left, right, res = 0, 0, 0\n",
    "            while True:\n",
    "                while left <len(nums) and nums[left] != 0:\n",
    "                    left +=1\n",
    "                right = left\n",
    "                while right < len(nums) and nums[right] != 1:\n",
    "                    right += 1\n",
    "                print(left, right)\n",
    "                res += ((right-left) * (right-left+1))//2\n",
    "                print(res)\n",
    "                if right >= len(nums):\n",
    "                    break\n",
    "                left = right\n",
    "            return res\n",
    "        left, right = 0, 0\n",
    "        cnt1 = 0\n",
    "        while right<len(nums) and  cnt1 < goal:\n",
    "            print(right, cnt1)\n",
    "            if nums[right] == 1:\n",
    "                cnt1 += 1\n",
    "                if cnt1 == goal:\n",
    "                    break\n",
    "            right += 1\n",
    "        if right == len(nums):\n",
    "            return 0\n",
    "        left_cnt0, right_cnt0 = 0, 0\n",
    "        res = 0\n",
    "        print(\"a\",left, right)\n",
    "        while True:\n",
    "            print(left, right)\n",
    "            right += 1\n",
    "            while right < len(nums) and nums[right] != 1 :\n",
    "                right += 1\n",
    "                right_cnt0 += 1\n",
    "            while left < len(nums) and nums[left] != 1:\n",
    "                left += 1\n",
    "                left_cnt0 += 1\n",
    "            print(\"b\",left, right)\n",
    "            print(\"c\",left_cnt0, right_cnt0)\n",
    "            res += (left_cnt0+1)*(right_cnt0+1)\n",
    "            left_cnt0, right_cnt0 = 0, 0\n",
    "            left+=1\n",
    "            if right == len(nums):\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        # 每一串最小符合长度的子串，左右两边的0的数量+1 ，再相乘就是对答案的贡献\n",
    "        cnt0 = [1]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                cnt0[-1] += 1\n",
    "            else:\n",
    "                cnt0.append(1)\n",
    "        # 特殊情况\n",
    "        if goal == 0:\n",
    "            return sum(comb(x, 2) for x in cnt0)\n",
    "        return sum(cnt0[i] * cnt0[i + goal] for i in range(len(cnt0) - goal))\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        # 每一串最小符合长度的子串，左右两边的0的数量+1 ，再相乘就是对答案的贡献\n",
    "        cnt0 = [1]\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if nums[i] == 0:\n",
    "                cnt0[-1] += 1\n",
    "            else:\n",
    "                cnt0.append(1)\n",
    "        # 特殊情况\n",
    "        if goal == 0:\n",
    "            return sum(comb(x, 2) for x in cnt0)\n",
    "        return sum(cnt0[i] * cnt0[i + goal] for i in range(len(cnt0) - goal))\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        left1 = 0\n",
    "        left2 = 0\n",
    "        \n",
    "        sum1 = 0\n",
    "        sum2 = 0\n",
    "        ret = 0\n",
    "        for right in range(len(nums)):\n",
    "            sum1 += nums[right]\n",
    "            while left1 <= right and sum1 > goal:\n",
    "                sum1 -= nums[left1]\n",
    "                left1 +=1\n",
    "            sum2 += nums[right]\n",
    "            while left2 <= right and sum2 >= goal:\n",
    "                sum2 -= nums[left2]\n",
    "                left2 += 1\n",
    "            ret += left2 - left1\n",
    "        return ret\n",
    "\n",
    "\n",
    "        '''\n",
    "        sum_value = 0\n",
    "        ret = 0\n",
    "        count = {}\n",
    "        for i in range(len(nums)):\n",
    "            sum_value += nums[i]\n",
    "            target =  sum_value - goal\n",
    "            if target in count:\n",
    "                ret += count[target]\n",
    "            \n",
    "            if sum_value in count:\n",
    "                count[sum_value] += 1\n",
    "            else:\n",
    "                count[sum_value] = 1\n",
    "            \n",
    "        if goal in count:\n",
    "            ret += count[goal]\n",
    "        return ret\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        #连续子数组简单的多，前缀和\n",
    "        n = len(nums)\n",
    "        sums = [0 for _ in range(len(nums)+1)]\n",
    "        for i in range(len(nums)):\n",
    "            sums[i+1] = sums[i]+nums[i]\n",
    "        #print(sums)\n",
    "\n",
    "        #2.53/60超时，没注意数字全是0或1\n",
    "        res = 0\n",
    "        '''\n",
    "        for i in range(1,n+1):\n",
    "            for j in range(i):\n",
    "                if sums[i]-sums[j] ==goal:\n",
    "                    res +=1\n",
    "                res = 0\n",
    "        '''\n",
    "        #3.优化，还是不行\n",
    "        '''\n",
    "        for i in range(1,n+1):\n",
    "            if sums[i]<goal:\n",
    "                continue\n",
    "            for j in range(i):\n",
    "                if sums[i]-sums[j] ==goal:\n",
    "                    res +=1\n",
    "                elif sums[i]-sums[j]<goal:\n",
    "                    break\n",
    "        '''\n",
    "\n",
    "\n",
    "        #4.直接记录每个1的位置，及首位1前0的个数\n",
    "        pos = [-1]\n",
    "        for i,x in enumerate(nums):\n",
    "            #print(x,i)\n",
    "            if x==1:\n",
    "                pos.append(i)\n",
    "        pos.append(n)     #首尾0.n-1\n",
    "        #print(pos)\n",
    "        \n",
    "        if goal>0:\n",
    "            for i in range(goal,len(pos)-1):\n",
    "                res +=(pos[i-goal+1]-pos[i-goal])*(pos[i+1]-pos[i])\n",
    "        else:\n",
    "            #pos[0],pos[-1] = 0,n-1\n",
    "            for i in range(1,len(pos)):\n",
    "                t = pos[i]-pos[i-1]-1\n",
    "                res += t*(t+1)//2\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def jie(num):\r\n",
    "    res=0\r\n",
    "    for i in range(1,num+1):\r\n",
    "        res+=i\r\n",
    "    return res\r\n",
    "class Solution:\r\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\r\n",
    "        idxs=[-1]\r\n",
    "        n=len(nums)\r\n",
    "        for i,num in enumerate(nums):\r\n",
    "            if num==1:\r\n",
    "                idxs.append(i)\r\n",
    "        idxs.append(n)\r\n",
    "        res=0\r\n",
    "        print(idxs)\r\n",
    "        if goal==0:\r\n",
    "            for i in range(1,len(idxs)):\r\n",
    "                res+=jie(idxs[i]-idxs[i-1]-1)\r\n",
    "            return res\r\n",
    "        for i in range(1,len(idxs)-goal):\r\n",
    "            res+=(idxs[i]-idxs[i-1])*(idxs[i+goal]-idxs[i+goal-1])\r\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        oneStack = [-1]\n",
    "        cnt = 0\n",
    "        for i, num in enumerate(nums):\n",
    "            if num: oneStack.append(i)\n",
    "        oneStack.append(len(nums))\n",
    "        if goal == 0:\n",
    "            for i in range(1, len(oneStack)):\n",
    "                cnt += (oneStack[i] - oneStack[i-1] - 1) * (oneStack[i] - oneStack[i-1]) // 2\n",
    "            return cnt\n",
    "\n",
    "        if len(oneStack) < goal + 2:\n",
    "            return 0\n",
    "         \n",
    "        for i in range(1, len(oneStack)-goal):\n",
    "            cnt += (oneStack[i]-oneStack[i-1]) * (oneStack[i+goal]-oneStack[i+goal-1])\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        ans=0\n",
    "        hs=[0]*30000*2\n",
    "        for i in range(1,len(nums)):\n",
    "            nums[i]+=nums[i-1]\n",
    "        hs[0+goal]=1\n",
    "        for num in nums:\n",
    "            ans+=hs[num]\n",
    "            hs[num+goal]+=1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = 0\n",
    "        memo = {}\n",
    "        ans = 0\n",
    "        memo[0] = 1\n",
    "        for i in range(n):\n",
    "            presum += nums[i]\n",
    "            if presum - goal in memo:\n",
    "                ans += memo[presum - goal]\n",
    "            memo[presum] = memo.get(presum, 0) + 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        prefixSum = 0\n",
    "        hashset = defaultdict(int)\n",
    "        hashset[0]=1\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            prefixSum += nums[i]\n",
    "            last = prefixSum - goal\n",
    "            res+=hashset[last]\n",
    "            hashset[prefixSum]+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "\n",
    "        pres = ans = 0\n",
    "        d = Counter()\n",
    "        d[0] = 1\n",
    "\n",
    "        for num in nums:\n",
    "            pres += num\n",
    "            ans += d[pres - goal]\n",
    "            d[pres] += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "'''\n",
    "给你一个二元数组 nums ，和一个整数 goal ，请你统计并返回有多少个和为 goal 的 非空 子数组。\n",
    "1 <= nums.length <= 3 * 104\n",
    "nums[i] 不是 0 就是 1\n",
    "0 <= goal <= nums.length\n",
    "'''\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        f = {}\n",
    "        sum_nums = 0\n",
    "        count = 0\n",
    "        f[0] = 1\n",
    "        for x in nums:\n",
    "            sum_nums += x\n",
    "            count += f[sum_nums - goal] if sum_nums - goal in f else 0\n",
    "            f[sum_nums] = f.get(sum_nums, 0) + 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        res, total, l = 0, 0, 0\n",
    "        prefix = defaultdict(int)\n",
    "        prefix[0] = 1\n",
    "        for r, n in enumerate(nums):\n",
    "            total += n\n",
    "            if total - goal in prefix:\n",
    "                res += prefix[total - goal] \n",
    "            prefix[total] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        res = 0\n",
    "        pre = 0\n",
    "        cache = collections.defaultdict(int)\n",
    "        cache[0] = 1\n",
    "        for i, n in enumerate(nums):\n",
    "            pre += n\n",
    "            res += cache[pre-goal]\n",
    "            cache[pre] += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        d_ = defaultdict(int)\n",
    "        lst = [0]\n",
    "        for i in nums:\n",
    "            lst.append(lst[-1]+i)\n",
    "        \n",
    "        res = 0\n",
    "        \n",
    "        for i in lst:\n",
    "            if i>=goal:\n",
    "                res+=d_[i-goal]\n",
    "            else:\n",
    "                res+=d_[i+goal]\n",
    "            d_[i]+=1\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        arr=list(accumulate(nums,initial=0))\n",
    "        x=defaultdict(int)\n",
    "        n=len(arr)\n",
    "        ans=0\n",
    "        for v in arr:\n",
    "            if v in x:\n",
    "                ans+=x[v]\n",
    "            x[v+goal]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        arr=list(accumulate(nums,initial=0))\n",
    "        x=defaultdict(int)\n",
    "        n=len(arr)\n",
    "        ans=0\n",
    "        for v in arr:\n",
    "            if v in x:\n",
    "                ans+=x[v]\n",
    "            x[v+goal]+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:\n",
    "        n = len(nums)\n",
    "        presum = [0] + list(accumulate(nums))\n",
    "        hashmap = defaultdict(int, {0:1})\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            r = presum[i+1]\n",
    "            l = r - goal\n",
    "            ans += hashmap[l]\n",
    "            hashmap[r] += 1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
